//给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 
//
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 
//
// 
// 
//
// 必须在不使用库的sort函数的情况下解决这个问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [2,0,1]
//输出：[0,1,2]
// 
//
// 
//
// 提示： 
//
// 
// n == nums.length 
// 1 <= n <= 300 
// nums[i] 为 0、1 或 2 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以不使用代码库中的排序函数来解决这道题吗？ 
// 你能想出一个仅使用常数空间的一趟扫描算法吗？ 
// 
// Related Topics 数组 双指针 排序 👍 1331 👎 0

package leetcode.editor.cn;

class SortColors {
    public static void main(String[] args) {
        Solution solution = new SortColors().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 归并排序
        /*public void sortColors(int[] nums) {
            mergeSort(nums, 0, nums.length - 1);
        }

        public void mergeSort(int[] nums, int left, int right) {
            if (left >= right) {
                return;
            }

            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);

            int[] temp = new int[right - left + 1];
            for (int i = left; i <= right; i++) {
                temp[i - left] = nums[i];
            }

            int i = 0, j = mid - left + 1;
            for (int k = left; k <= right; k++) {
                if (i == mid - left + 1) {
                    nums[k] = temp[j++];
                } else if (j == right - left + 1 || temp[i] <= temp[j]) {
                    nums[k] = temp[i++];
                } else {
                    nums[k] = temp[j++];
                }
            }
        }*/

        // 单指针（2次遍历）
        /*public void sortColors(int[] nums) {
            int n = nums.length, ptr = 0;

            // 将0放在前面
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) {
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ptr++;
                }
            }

            // 将1放在0的后面
            for (int i = ptr; i < nums.length; i++) {
                if (nums[i] == 1) {
                    int temp = nums[i];
                    nums[i] = nums[ptr];
                    nums[ptr] = temp;
                    ptr++;
                }
            }
        }*/

        public void sortColors(int[] nums) {
            int n = nums.length, p1 = 0, p0 = 0;
            for (int i = 0; i < n; i++) {
                if (nums[i] == 1) {
                    int temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                    p1++;
                }

                else if (nums[i] == 0) {
                    int temp = nums[i];
                    nums[i] = nums[p0];
                    nums[p0] = temp;
                    // 此时交换出去的一定是1，所以需要把1交换在p1位置
                    if (p0 < p1) {
                        temp = nums[i];
                        nums[i] = nums[p1];
                        nums[p1] = temp;
                    }
                    p0++;
                    p1++;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}
